#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct BinaryTree{
    int data;
    struct BinaryTree* left;
    struct BinaryTree* right;
}BTNode;

BTNode* createNode(int n){
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if(newNode == NULL){
        printf("error assign!");
        exit(1);
    }
    newNode->data = n;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insertBTNode(BTNode** root, BTNode* newNode){
    if(*root == NULL){
        *root = newNode;
        return;
    }
    if(newNode->data < (*root)->data){
        if((*root)->left == NULL){
            (*root)->left = newNode;
        }else{
            insertBTNode(&((*root)->left), newNode);
        }
    }else{
        if((*root)->right == NULL){
            (*root)->right = newNode;
        }else{
            insertBTNode(&((*root)->right), newNode);
        }
    }
}
void preOrder(BTNode* root){
    if(root == NULL){
        return;
    }
    printf("%d ",root->data);
    preOrder(root->left);
    preOrder(root->right);
}


void inOrder(BTNode* root){
    if(root == NULL){
        return;
    }
    inOrder(root->left);
    printf("%d ",root->data);
    inOrder(root->right);
}

void postOrder(BTNode* root){
    if(root == NULL){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ",root->data);
}


int BTSize(BTNode* root){
    if(root == NULL){
        return 0;
    }
    return 1+BTSize(root->left) +BTSize(root->right);
}

int getHeight(BTNode* root){
    if(root == NULL){
        return 0;
    }
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    return l > r ? l + 1 : r + 1;
}

void printLevel(BTNode* root,int level){
    if(root == NULL) return;
    if(level == 1) {
        printf("%d ",root->data);
    }else if(level > 1){
        printLevel(root->left,level-1);
        printLevel(root->right,level-1);
    }
}

void levelOrder(BTNode* root){
    int h = getHeight(root);
    for(int i = 1; i <= h;i++){
        printLevel(root,i);
    }
}



int main(){
    BTNode* root = createNode(10);
    insertBTNode(&root, createNode(5));
    insertBTNode(&root, createNode(15));
    insertBTNode(&root, createNode(3));
    insertBTNode(&root, createNode(7));
    insertBTNode(&root, createNode(12));
    insertBTNode(&root, createNode(18));

    printf("PreOrder: ");
    preOrder(root);
    printf("\n");

    printf("InOrder: ");
    inOrder(root);
    printf("\n");

    printf("PostOrder: ");
    postOrder(root);
    printf("\n");

    printf("LevelOrder: ");
    levelOrder(root);
    printf("\n");

    printf("Size: %d\n", BTSize(root));
    printf("Height: %d\n", getHeight(root));
}